//
//  main.cpp
//  Random3
//
//  Created by chenyh on 2021/2/19.
//

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define MAX 101

/**输入函数*/
void input(int num[])
{
    int i;
    srand((unsigned)time(NULL));//得到随机种子
    for (i = 1; i<MAX; i++) {
        num[i] = rand()%100;    //生成100以内的随机数
    }
    
}

/**输出函数*/
void output(int num[])
{
    int i;
    for (int i=1; i<MAX; i++) {
        cout<<num[i]<<"  ";
        if (0==i%10) {
            cout<<endl;
        }
    }
}
//简单查找函数
int find(int num[],int x)
{
    int i;
    for (i=1; i<MAX; i++) {
        if (x==num[i]) {    //遍历查找指定数字的位置
            return i;
        }
    }
    return 0;
}

//快速排序
void sort(int num[],int low,int high) {
    int l,h;
    if (low < high) {
        l=low;
        h=high;
        num[0]=num[l]; //save pivot
        while (l<h) {
            while(l<h && num[h]>=num[0]) h--; //利用快速排序使数据有序 num[l]=num[h];
            while(l<h && num[l]<=num[0]) l++;
            num[h]=num[l];
        }
        num[l]=num[0];
        sort(num, low, l-1);
        sort(num, l+1, high);
    }
}
//折半查找函数
int find(int num[],int x,int low,int high)
{
    int mid;//中间位置
    while (low<=high) {
        mid=(low+high)/2;
        if (x==num[mid]) {
            return mid;
        }
        else if (x <num[mid] ) {
            high=mid-1;
        }else {
            low=mid+1;
        }
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    int x, pos, num[MAX];
    input(num);
    cout<<"随机生成的数字: "<<endl;
    output(num);
    cout<<"请输入要查找的数字"<<endl;
    cin>>x;
    pos=find(num, x);
    if(pos)
        cout<<"OK!"<<x<< "is found in pos: "<< pos<<endl;
    else
        cout<<"OK!"<<x<< "is found in pos: "<<endl;
    return 0;
}
